////
////  main.c
////  线索二叉树tree
////
////  Created by Song on 2018/3/26.
////  Copyright © 2018年 Song. All rights reserved.
////
//
#include <stdio.h>
#include <stdlib.h>

typedef char ElemType;
typedef enum {Link,Thread} childTag; 	//Link表示结点，Thread表示线索
typedef struct bitNode
{
    ElemType data;
    struct bitNode *lchild, *rchild;
    int ltag, rtag;
} bitNode, *bitTree;

bitTree pre; 							//创建全局变量。表示刚刚訪问过的结点



/*
 创建二叉树，其输入必须依照前序遍历的次序。
 
 T：二叉树根节点
 arr：依照前序遍历次序排列的各节点的值。无孩子结点时用空格取代
 */
void create_tree(bitTree *T, char **arr)
{
    char c;
    sscanf(*arr,"%c",&c); 						//读入一个结点值
    (*arr)++;
    if(' '== c) 									//假设是空格，表示空结点
    {
        *T=NULL;
    }
    else
    {
        *T=(bitTree)malloc(sizeof(bitNode)); 		//构造新结点
        (*T)->data=c;
        (*T)->ltag=Link;
        (*T)->rtag=Link;
        create_tree(&(*T)->lchild,arr);			//构造新结点的左孩子
        create_tree(&(*T)->rchild,arr);			//构造新结点的右孩子
    }
}


/*
 訪问结点信息
 */
void visit(bitTree T)
{
    printf("| %d | %c | %d |\n",T->ltag,T->data,T->rtag);
}


/*
 前序遍历訪问二叉树
 */
void pre_order_traverse(bitTree T,int level)
{
    if(T)
    {
        visit(T);
        pre_order_traverse(T->lchild,level+1);
        pre_order_traverse(T->rchild,level+1);
    }
}

/*
 中序遍历二叉树，对其进行线索化
 */
void in_order_threading(bitTree T)
{
    if(T)
    {
        in_order_threading(T->lchild); 			//左孩子线索化
        if(!T->lchild) 							//假设左孩子为空，则将其指向直接前驱
        {
            T->lchild=pre;
            T->ltag=Thread;
        }
        if(!pre->rchild) 							//假设上一个结点的右孩子为空，则将其指向直接后继。（注意：仅仅有訪问到下一个结点时，才会知道本结点的后继是谁）
        {
            pre->rchild=T;
            pre->rtag=Thread;
        }
        pre=T;
        in_order_threading(T->rchild); 			//右孩子线索化
    }
}

/*
 增加一个头结点，使二叉线索树成一个封闭环
 P：带有头结点的二叉树。头结点的左孩子指向二叉树T；右孩子指向T树中的最后一个叶子结点
 T：不带有头结点的二叉树。
 
 
 */
void in_thread(bitTree *P,bitTree T)
{
    (*P)=(bitTree)malloc(sizeof(bitNode)); 		//构造新增加的头结点
    (*P)->ltag=Link;
    (*P)->rtag=Thread;
    (*P)->rchild=*P;
    if(!T) 										//假设二叉树为空，则P的孩子指向自己。
    {
        (*P)->lchild=*P;
    }
    else
    {
        (*P)->lchild=T;
        pre=*P;
        in_order_threading(T); 					//对二叉树进行线索化
        (*P)->rchild=pre; 						//将头结点右孩子指向最后一个叶子结点
        pre->rtag=Thread; 						//将最后一个叶子结点的右孩子指向头结点。这样。环就形成了。
        
        
        pre->rchild=*P;
    }
}

/*
 非递归方式：中序遍历二叉树(树必须带有头结点，且已经线索化)
 P:带有头结点的二叉树
 */
void in_order_traverse(bitTree P)
{
    bitTree T;
    T=P->lchild;
    while(T!=P) 									//推断是否空树
    {
        while(T->ltag==Link) 						//从左孩子開始。直到叶子结点
        {
            T=T->lchild;
        }
        visit(T);
        while(T->rtag==Thread && T->rchild!=P) //依据线索，訪问后继结点。而且后继结点不是指向头结点的
        {
            T=T->rchild;
            visit(T);
        }
        T=T->rchild;
    }
}


int main()
{
    bitTree P,T;
    int level =1; 					//表示该结点的深度
    char *arr="ab d  ce   "; 			//构造二叉树所需结点(按前序遍历方式输入)
    create_tree(&T,&arr); 			//构造二叉树
    printf("pre_order_traverse:先序遍历：\n");
    pre_order_traverse(T,level); 		//前序遍历输出二叉树
    printf("in_order_traverse：中序遍历：\n");
    in_thread(&P,T); 					//二叉树线索化
    in_order_traverse(P); 			//输出线索化后的二叉树
    return 0;
}



// 错误代码
void test(){
    //#include <string.h>
    //
    //typedef enum  {
    //    Link, // link == 0 表示指向左右孩子指针
    //    Thread // thread == 1 表示指向前驱或后继的线索
    //}PointerTag;
    //
    //typedef struct BiThrNode {
    //    char data;
    //    struct BiThrNode *lchild,*rchild;
    //    PointerTag lTag, rTag;
    //}BiThrNode, *BiThrTree;
    //
    ////BiThrTree pre; // 全局变量，始终指向刚刚访问过的节点
    //
    //
    //
    //// 中序线索化
    //void inThreadingg(BiThrTree p,BiThrTree pre) {
    //    if (p) {
    //        inThreadingg(p->lchild,pre); // 递归左子树线索化
    //
    //        if (!p->lchild) { // 当前节点的左孩子为空
    //            p->lTag = Thread; // 前驱线索
    //            p->lchild = pre; // 左孩子指针指向前驱
    //        }
    //        if (!pre->rchild) { // 前驱没有右孩子
    //            pre->rTag = Thread; // 后继线索
    //            pre->rchild = p; // 前驱右孩子指针指向后继（当前节点 p）
    //        }
    //        pre = p; // 保持pre指向p的前驱
    //
    //        inThreadingg(p->rchild,pre); // 递归右子树线索化
    //    }
    //}
    //
    //// 中序线索化(加头结点)
    //void inOrderThreading(BiThrTree t,BiThrTree thrT) {
    //    thrT = (BiThrTree)malloc(sizeof(BiThrNode));
    //    thrT->lTag = Link;
    //    thrT->rTag = Thread;
    //    if(!t){//如果二叉树为空树，则Thrt->lchild指针回指
    //        thrT->lchild = thrT;
    //        thrT->rchild = thrT;//右指针回指
    //    }else{
    //        thrT->lchild = t;
    //        BiThrNode *pre = thrT;//pre指针总指向当前结点的前驱结点
    //        inThreadingg(t, pre);
    //        //继续为最后一个结点加入线索
    //        //此时pre应指向最后一个结点
    //        pre->rTag = Thread; // 后继
    //        pre->rchild = thrT;//最后一个结点的rchild域指针回指
    //        thrT->rchild = pre;//头结点的rchild域指针指向最后一个结点
    //    }
    //}
    //
    //// 中序遍历 (非递归)
    //void inOrderTraversePrint(BiThrTree t) {
    //    BiThrNode *p = t->lchild; // p 指向根节点
    //    while (p!=t) {
    //        while (p->lTag == Link) {
    //            p = p->lchild;
    //        }
    //        printf("%c",p->data);
    //        while (p->rTag == Thread && p->rchild != t) {
    //            p = p->rchild;
    //            printf("%c",p->data);
    //        }
    //        p = p->rchild;
    //    }
    //    printf("\n");
    //}
    //
    //// 创建二叉树
    ////void creatBiTree(BiThrTree t) {
    ////    char ch;
    ////    scanf("%c",&ch);
    ////    if (ch == '#') {
    ////        t = NULL;
    ////    }else {
    ////        t = (BiThrTree)malloc(sizeof(BiThrNode));
    ////        t->data = ch;
    ////        creatBiTree(t->lchild);
    ////        creatBiTree(t->rchild);
    ////    }
    ////}
    //void creatTree(BiThrTree *tP) {
    //    char ch;
    //    scanf("%c",&ch);
    //    if (ch == '#') {
    //        *tP = NULL;
    //    } else {
    //        *tP = (BiThrTree)malloc(sizeof(BiThrNode));
    //        if (!*tP) { exit(0); }
    //        (*tP)->data = ch;
    //        creatTree(&(*tP)->lchild);
    //        creatTree(&(*tP)->rchild);
    //    }
    //}
    //
    //int main(int argc, const char * argv[]) {
    //    
    //    BiThrTree t;
    //    
    //    printf("输入：\n");
    //    creatTree(&t);
    //    
    //    
    //    BiThrTree thrT;
    //    inOrderThreading(t, thrT);
    //    inOrderTraversePrint(t);
    //    
    //    return 0;
    //}
    
}
